/**
 * @作者 钟先崟
 * @时间 2023-03-05 13:39
 * @说明 141. 环形链表
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = head;
        System.out.println(hasCycle(head));
    }

    /**
     * 快慢指针乌龟兔子法
     *执行用时：
     * 0 ms
     * , 在所有 Java 提交中击败了
     * 100.00%
     * 的用户
     * 内存消耗：
     * 42.3 MB
     * , 在所有 Java 提交中击败了
     * 78.33%
     * 的用户
     * @param head
     * @return
     */
//    public static boolean hasCycle(ListNode head) {
//        if (head == null) return false;
//        ListNode turtle = head;
//        ListNode rabbit = head.next;
//        while (rabbit != null) {
//            if (rabbit == turtle) return true;
//            turtle = turtle.next;
//            rabbit = rabbit.next;
//            if (rabbit == null) return false;
//            if (rabbit == turtle) return true;
//            rabbit = rabbit.next;
//        }
//        return false;
//    }

    /**
     * 题目链表最长为10*10*10*10个节点，所以只需要记录链表是否可以next 10000次就可以判断是否有环形了
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：42.3 MB , 在所有 Java 提交中击败了81.85%的用户
     *
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null) return false;
        int num = 0;
        while (true) {
            head = head.next;
            if (head == null) return false;
            num++;
            if (num > 10000) return true;
        }
    }
}
